Error diffusion is a well-known halftone method in which continuous tone or “contone” color image input data values are converted to binary values that are able to be printed on paper or other recording media using a xerographic, ink-jet, solid-ink or other color marking device that outputs each colorant in a binary fashion, i.e. each colorant channel is either “off” (not output) or “on” (output) or for each pixel location in the output image. Each contone input pixel value (e.g., ranging between 0 to 1 or between 0 to 255 or other range that can vary) is “quantized” by comparing its value relative to a threshold and the corresponding output pixel in the printed image is set to “on” or “off” depending upon whether the threshold is satisfied or not. The “error” by which the contone input pixel value differs the binary output value is propagated or “diffused” to future input pixels yet to be quantized, such that the error is accounted for in future processing and, thus, is preserved and influences later quantization operations and the appearance of the resulting output image.
For black-and-white (or other monochrome) images, the error is propagated to future pixels in the same row and/or different rows using various known techniques. Color images are relatively more complex. In “scalar” or “separable” error diffusion, the input images for each color plane or separation of the color image are processed as individual monochrome images in a manner similar to black-and-white images.
Another color error diffusion technique is “vector” error diffusion, which generally produces higher-quality printed output. Vector error diffusion operates in a selected color space. Each input value is located in the color space as defined by its coordinates. Each input color value is mapped to a set of possible output values within the color space, and the closest member of the set of possible output values is selected as the output value. The resulting error, defined by the difference from the input coordinates to the output coordinates, is propagated to the next input value. A drawback of vector error diffusion is the increased computational complexity and resulting need for data buffers.
Traditional vector error diffusion methods operate in the output color space (e.g., CMYK). Specifically, all input, modified input (input+error), output and error values are specified in CMYK (CMYK is used herein as an example of an output color space, but others are possible as generally known in the art). While these methods generally result in output images of good quality, main challenges presented include: (i) elegant treatment of black (K); (ii) uniform distribution of the darkest colorant dots (i.e., the mixture of black (K) and blue (M+C=M overlapped with C); (iii) minimization of artifacts due to accumulation of errors.
More recently, Hierarchical Error Diffusion (HED) has been implemented. In HED, the CMYK signals are first converted to CMYKRGB color space using Minimum Brightness Variation Criterion (MBVC), and the remaining calculations (modified input generation, output determination, error calculation) are performed in the CMYKRGB color space. The output is generated in a hierarchical fashion from darker dots to lighter dots. HED provides significant improvements in image quality, but requires a seven channel buffer to store errors in CMYKRGB (instead of a four channel buffer for CMYK). This substantially increases the cost for the machines that implement halftoning in hardware.
Memory Efficient Hierarchical Error Diffusion (MEHED) has also been proposed. Unlike original HED, it uses a four channel CMYK error buffer. The conversion from CMYK to CMYKRGB is performed on modified input values (input+error) instead of on the (original) input values, and the resulting CMYKRGB error is converted back to CMYK color space. A main technical difficulty is the color space conversion for the modified input, because the modified input can be <0 (negative) or >1, which are beyond the range required for MBVC. Thus, MEHED decomposes the modified input into three parts: (i) negative; (ii) regular; (iii) surplus and carefully shares information among these three parts. An advantage of MEHED over HED is that it does not require additional buffering space. A main disadvantage is the high computational complexity which increases machine cost and processing time. Overall image quality for MEHED is comparable to HED. Because MEHED is sub-optimal with respective to MBVC, it is slightly less smooth than HED for uniform color or slowing varying color. On the other hand, MEHED is also slightly less sensitive to noise in rough (high texture) areas.